import java.util.ArrayDeque;
import java.util.ArrayList;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: wangxin
 * Date: 2024-11-24
 * Time: 21:22
 */
public class test2 {
    //解法一
    public ArrayList<Integer> maxInWindows (int[] num, int size) {
        // write code here
        ArrayList<Integer> res = new ArrayList<>();
        if(size > num.length||size == 0){
            return res;
        }

        for(int i = 0;i< num.length - size+1;i++){
            int max = Integer.MIN_VALUE;
            for(int j = i;j < size + i;j++){
                max = Math.max(max,num[j]);
            }
            res.add(max);
        }

        return res;
    }
    //解法二
    public ArrayList<Integer> maxInWindows2 (int[] num, int size) {
        // write code here
        ArrayList<Integer> res = new ArrayList<>();
        if(size <= num.length&&size != 0){
            ArrayDeque<Integer> ad = new ArrayDeque<>();
            for(int i = 0;i < size;i++){
                while(!ad.isEmpty()&&num[ad.peekLast()]< num[i])
                    ad.pollLast();
                ad.add(i);
            }
            for(int i = size;i < num.length;i++){
                res.add(num[ad.peekFirst()]);
                while(!ad.isEmpty()&&ad.peekFirst()< i - size + 1)
                    ad.pollFirst();
                while(!ad.isEmpty()&&num[ad.peekLast()]< num[i])
                    ad.pollLast();
                ad.add(i);
            }
            res.add(num[ad.pollFirst()]);
        }
        return res;
    }
}
